package main

import "fmt"

// TreeNode 定义二叉树的节点
type TreeNode struct {
	Value interface{}
	Left  *TreeNode
	Right *TreeNode
}

// Tree 定义二叉树
type Tree struct {
	Root *TreeNode
}

// InorderTraversal 实现中序遍历  左根右
func (t *Tree) InorderTraversal(node *TreeNode) {
	if node != nil {
		t.InorderTraversal(node.Left)  // 递归遍历左子树
		fmt.Println(node.Value)        // 访问当前节点
		t.InorderTraversal(node.Right) // 递归遍历右子树
	}
}

// PreorderTraversal 实现前序遍历  //根左右
func (t *Tree) PreorderTraversal(node *TreeNode) {
	if node != nil {
		fmt.Println(node.Value)         // 访问当前节点
		t.PreorderTraversal(node.Left)  // 递归遍历左子树
		t.PreorderTraversal(node.Right) // 递归遍历右子树
	}
}

// PostorderTraversal 后序遍历 左右根
func (t *Tree) PostorderTraversal(node *TreeNode) {
	if node != nil {
		t.PostorderTraversal(node.Left)  // 递归遍历左子树
		t.PostorderTraversal(node.Right) // 递归遍历右子树
		fmt.Println(node.Value)          // 访问当前节点
	}
}

func main() {
	// 创建一棵新的树
	root := &TreeNode{Value: 1}
	root.Left = &TreeNode{Value: 2}
	root.Right = &TreeNode{Value: 3}
	root.Left.Left = &TreeNode{Value: 4}
	root.Left.Right = &TreeNode{Value: 5}
	root.Right.Right = &TreeNode{Value: 6}
	root.Left.Left.Left = &TreeNode{Value: 7}
	root.Left.Right.Left = &TreeNode{Value: 8}
	root.Left.Right.Right = &TreeNode{Value: 9}

	// 创建一个树实例
	tree := &Tree{Root: root}

	// 执行中序遍历
	//tree.InorderTraversal(tree.Root)

	// 后续
	tree.PostorderTraversal(tree.Root)
}
